/* 
 * Evaluate Reverse Polish Notation
 * ["4", "13", "5", "/", "+"] -> (4+(13/5))->6
 */

#include "../func.h"

bool is_opearator(const string &op)
{
    return op.size() == 1 && string("+-*/").find(op) != string::npos;
}
int evalRPN(vector<string> &tokens)
{
    int x, y;
    auto token = tokens.back();
    tokens.pop_back();
    if (is_opearator(token))
    {
        y = evalRPN(tokens);
        x = evalRPN(tokens);
        if (token[0] == '+')
            x += y;
        else if (token[0] == '-')
            x -= y;
        else if (token[0] == '*')
            x *= y;
        else
            x /= y;
    }
    else
    {
        size_t i;
        x = stoi(token, &i);
    }
    return x;
}

int evalRPN2(vector<string> &tokens)
{
    stack<string> s;
    for (auto token : tokens)
    {
        if (!is_opearator(token))
            s.push(token);
        else
        {
            int y = stoi(s.top());
            s.pop();
            int x = stoi(s.top());
            s.pop();
            if (token[0] == '+')
                x += y;
            else if (token[0] == '-')
                x -= y;
            else if (token[0] == '*')
                x *= y;
            else
                x /= y;
            s.push(to_string(x));
        }
    }
    return stoi(s.top());
}